class Solution {
    vector<bool> checkCol, checkDig1, checkDig2;
    vector<vector<string>> ret;
    vector<string> path;
    int n;

public:
    Solution()
        : checkCol(10, false), checkDig1(20, false), checkDig2(20, false) {}

    vector<vector<string>> solveNQueens(int _n) {
        n = _n;
        path = vector<string>(n, string(n, '.'));

        dfs(0);
        return ret;
    }
    void dfs(int row) {
        if (row == n) {
            ret.push_back(path);
            return;
        }
        for (int col = 0; col < n; col++) // lie
        {
            if (!checkCol[col] && !checkDig1[row - col + n] &&
                !checkDig2[row + col]) {
                path[row][col] = 'Q';
                checkCol[col] = checkDig1[row - col + n] =
                    checkDig2[row + col] = true;
                dfs(row + 1);
                path[row][col] = '.';
                checkCol[col] = checkDig1[row - col + n] =
                    checkDig2[row + col] = false;
            }
        }
    }
};